#ifndef AVALON_ALGORITHM_HPP
#define AVALON_ALGORITHM_HPP
#include <deque>
#include <ostream>
#include <vector>
#include <map>
#include <set>
#include "Avalon/Base/Base.hpp"

namespace Avalon {

  //! Removes the first occurance of an element in a vector.
  /*!
    \param container The vector to remove the element from.
    \param element The element to remove.
  */
  template<typename T, typename U>
  bool Remove(std::vector<T>& container, const U& element) {
    typename std::vector<T>::iterator itemIterator = std::find(
      container.begin(), container.end(), element);
    if(itemIterator == container.end()) {
      return false;
    } else if(itemIterator != container.end() - 1) {
      std::swap(*itemIterator, container.back());
    }
    container.pop_back();
    return true;
  }

  //! Erases an element in a vector.
  /*!
    \param container The vector to erase the element from.
    \param location An iterator to the location of the element to delete.
  */
  template<typename T>
  typename std::vector<T>::iterator Erase(std::vector<T>& container,
      typename std::vector<T>::iterator location) {
    typename std::vector<T>::difference_type index =
      location - container.begin();
    if(location != container.end() - 1) {
      std::swap(*location, container.back());
    }
    container.pop_back();
    return container.begin() + index;
  }

  //! Erases all occurances of an element in a vector.
  /*!
    \param container The vector to erase all occurances of the element from.
    \param element The element to erase.
  */
  template<typename T, typename U>
  void EraseAll(std::vector<T>& container, const U& element) {
    container.erase(std::remove(container.begin(), container.end(), element),
      container.end());
  }

  //! Iterates over all elements of a container.
  /*!
    \param container The container to iterate over.
    \param function The function to call.
  */
  template<typename T, typename F>
  void ForEach(const T& container, const F& function) {
    for(typename T::const_iterator i = container.begin();
        i != container.end(); ++i) {
      function(*i);
    }
  }

  //! Clears a vector of pointers, deleting each element.
  /*!
    \param container The vector to clear.
  */
  template<typename T>
  void Clear(std::vector<T*>& container) {
    for(typename std::vector<T*>::iterator i = container.begin();
        i != container.end(); ++i) {
      delete *i;
      *i = NULL;
    }
    container.clear();
  }

  //! Clears a deque of pointers, deleting each element.
  /*!
    \param container The vector to clear.
  */
  template<typename T>
  void Clear(std::deque<T*>& container) {
    for(typename std::deque<T*>::iterator i = container.begin();
        i != container.end(); ++i) {
      delete *i;
      *i = NULL;
    }
    container.clear();
  }

  //! Clears a map of pointers, deleting each element.
  /*!
    \param container The map to clear.
  */
  template<typename K, typename V>
  void Clear(std::map<K, V*>& container) {
    for(typename std::map<K, V*>::iterator i = container.begin();
        i != container.end(); ++i) {
      delete i->second;
      i->second = NULL;
    }
    container.clear();
  }
}

//! Prints a vector to an ostream.
/*!
  \param out The stream to print to.
  \param value The vector to print.
  \return <i>out</i> for chaining purposes.
*/
template<typename T>
std::ostream& operator <<(std::ostream& out, const std::vector<T>& value) {
  out << "[";
  for(typename std::vector<T>::const_iterator i = value.begin();
      i != value.end(); ++i) {
    out << *i;
    if(i != value.end()) {
      out << ", ";
    }
  }
  out << "]";
  return out;
}

//! Prints a map to an ostream.
/*!
  \param out The stream to print to.
  \param value The vector to print.
  \return <i>out</i> for chaining purposes.
*/
template<typename K, typename V>
std::ostream& operator <<(std::ostream& out, const std::map<K, V>& value) {
  out << "{";
  for(typename std::map<K, V>::const_iterator i = value.begin();
      i != value.end(); ++i) {
    out << i->first << ": " << i->second;
    if(i != value.end()) {
      out << ", ";
    }
  }
  out << "}";
  return out;
}

//! Prints a set to an ostream.
/*!
  \param out The stream to print to.
  \param value The vector to print.
  \return <i>out</i> for chaining purposes.
*/
template<typename T>
std::ostream& operator <<(std::ostream& out, const std::set<T>& value) {
  out << "{";
  for(typename std::set<T>::const_iterator i = value.begin();
      i != value.end(); ++i) {
    out << *i;
    if(i != value.end()) {
      out << ", ";
    }
  }
  out << "}";
  return out;
}

#endif // AVALON_ALGORITHM_HPP
